정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
Karp-Rabin 알고리즘을 이용한 순위다중패턴매칭 알고리즘의 병렬 구현 |
| 영문제목(English Title) |
Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm |
| 저자(Author) |
박경빈
김영호
심정섭
Kyung Bin Park
Youngho Kim
Jeong Seop Sim
|
| 원문수록처(Citation) |
VOL 48 NO. 03 PP. 0249 ~ 0256 (2021. 03) |
한글내용
(Korean Abstract) |
길이가 같은 두 문자열은 각 문자의 상대적 순위가 모두 일치할 때 순위동형이라 한다. 순위다 중패턴매칭문제는 텍스트 T(|T|=n)와 패턴들의 집합 ~P = {P1, P2, … , Pk}가 주어졌을 때, ~P의 패턴들과 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 패턴들 중 가장 짧은 패턴의 길이를 m, 가장 긴 패턴 의 길이를 ~m, 모든 패턴들의 길이의 합을 M이라 하자. M ∈m^O(1) 인 경우 Karp-Rabin 알고리즘을 이용하여 탐색단계를 평균적으로 O(n) 시간에 수행하는 순위다중패턴매칭 알고리즘이 제시되었다. 본 논문에 서는 Karp-Rabin 알고리즘을 이용하여 순위다중패턴매칭문제를 병렬적으로 해결하는 구현 방법을 제시한다. 제시하는 병렬 구현은 전처리단계를 O(M)개의 스레드를 사용하여 평균적으로 O(~m) 시간에 수행하며, 탐색단계를 O(n)개의 스레드를 사용하여 평균적으로 O(m) 시간에 각각 수행한다. 무작위로 생성된 문자열에 대해 실험한 결과, n=1,000,000, k=1,000, m=5일 때 본 논문에서 제시하는 병렬 구현이 기존의 순차알고리즘보다 약 201.5배 빠르게 수행되었다.
|
영문내용
(English Abstract) |
When two strings of the same length have the same relative orders, they are called order-isomorphic. Given a text T(|T|=n) and a set of patterns ~P = {P1, P2, … , Pk}, the order-preserving multiple pattern matching problem is to find all substrings of T that are order-isomorphic to any pattern in ~P. Let m be the length of the shortest pattern, ~m be the length of the longest pattern, and M be the sum of lengths of all the patterns in ~P. When M is polynomial with respect to m , an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm was presented whose searching step runs in O(n) time on average. In this paper, we implemented an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm in parallel. It runs in O(m) time on average using O(n) threads in the preprocessing step and runs in O(m) time on average using O(n) threads in the searching step. The experimental results for random strings as input showed that our parallel implementation performed approximately 201.5 times faster than the existing sequential algorithm when n=1,000,000, k=1,000, m=5.
|
| 키워드(Keyword) |
순위다중패턴매칭
Karp-Rabin 알고리즘
병렬 구현
GPU
order-preserving multiple pattern matching
Karp-Rabin algorithm
parallel implementation
GPU
|
| 파일첨부 |
PDF 다운로드
|
